/********************************************************************
 * Filename:	MemoryManager.c
 * Description:  It manages the system and user memory, also loads 
 *              pages from backing store into RAM when needed.
 * Group 2:		nachOS
 * Author(s):	Daniel Fairweather
 *              Jan Durakiewicz
 *              Ying Wang
 * Class:		CSE 325
 * Instructor:	David Duggan
 * Assignment:	Lab #6 Page Replacement
 * Assigned:	4/2/2013
 * Due:			4/9/2013
 ********************************************************************/
 

#include "MemoryManager.h"
#include "LRU.h"


char RAM[RAM_SIZE/FRAME_SIZE][FRAME_SIZE] = {0};
char BS[BS_SIZE/FRAME_SIZE][FRAME_SIZE] = {0};
PageTable pageTable;
MetaTable metaTable;
SwapTable swapTable;

int replaceVar = 0;


void init(){
	int i = 0;

	/* Initialize the pageTable. */
	pageTable.nextAvailableIndex = 0;
	pageTable.freeRows = BS_SIZE/FRAME_SIZE;
	pageTable.freeEndRows = BS_SIZE/FRAME_SIZE;
	for(i = 0; i < BS_SIZE/FRAME_SIZE; i++){
		pageTable.row[i] = 0;
	}

	/* Initialize the metaTable. */
	metaTable.freeRows = NUM_PAGETABLES;
	for(i = 0; i < NUM_PAGETABLES; i++){
		metaTable.row[i][0] = BS_SIZE/FRAME_SIZE;
		metaTable.row[i][1] = BS_SIZE/FRAME_SIZE;
	}

	/* Intialize the swapTable. */
	for(i = 0; i < (RAM_SIZE/FRAME_SIZE)-NUM_SYSTEM_FRAMES; i++){
		swapTable.row[i] = BS_SIZE/FRAME_SIZE;
	}

	/* Intialize the useTable. */
    for(i = 0; i < USE_TABLE_SIZE; i++){
		set_use_table_at(i, 0);
	}

	init_LRU();
}


int allocateFrames(int numberOfPages){
	int i = 0;
	int j = 0;
	int framesAllocated = 0;
	int metaRow = 0;

	/* Do some error checking here... */
	if(numberOfPages <= 0){
		return(-1);
	}
	else if(numberOfPages > pageTable.freeRows){
		return(-2);
	}
	else if(metaTable.freeRows == 0){
		return(-3);
	}
	else if(numberOfPages > pageTable.freeEndRows){
		squishPageTable();
		return(allocateFrames(numberOfPages));
	}

	/* Reserve a metaTable row. */
	for(i = 0; i < NUM_PAGETABLES; i++){
		if(metaTable.row[i][0] == BS_SIZE/FRAME_SIZE){
			metaRow = i;
			metaTable.freeRows--;
			metaTable.row[i][0] = pageTable.nextAvailableIndex;
			metaTable.row[i][1] = pageTable.nextAvailableIndex + numberOfPages - 1;
			pageTable.freeRows -= numberOfPages;
			pageTable.freeEndRows -= numberOfPages;
			pageTable.nextAvailableIndex = pageTable.nextAvailableIndex + numberOfPages;
			break;
		}
	}

	for(i = 0; i < BS_SIZE/FRAME_SIZE; i++){
		if(get_use_table_at(i) == 0){
			set_use_table_at(i, 1);
			set_page_address(&pageTable.row[metaTable.row[metaRow][0]+framesAllocated],i);
			set_page_validity(&pageTable.row[metaTable.row[metaRow][0]+framesAllocated],1);
			framesAllocated++;
			if(framesAllocated == numberOfPages){
				break;
			}
		}
	}

	return(metaRow);
}


int deallocateTable(int pageTableID){
	int framesDeallocated = 0;
	int numberOfPages = metaTable.row[pageTableID][1] - metaTable.row[pageTableID][0] + 1;

	if(metaTable.row[pageTableID][0] == BS_SIZE/FRAME_SIZE || pageTableID < 0){
		return(-1);
	}

	pageTable.freeRows += numberOfPages;

	if(pageTable.nextAvailableIndex == metaTable.row[pageTableID][1] + 1){
		pageTable.nextAvailableIndex = metaTable.row[pageTableID][0];
		pageTable.freeEndRows += numberOfPages;
	}

	while(framesDeallocated != numberOfPages){
		unsigned short int logicalpage = metaTable.row[pageTableID][0]+framesDeallocated;
		int physicalPage = get_page_address(&pageTable.row[logicalpage]);
		set_use_table_at(physicalPage, 0);
		pageTable.row[logicalpage] = 0;
		framesDeallocated++;
	}
	metaTable.row[pageTableID][0] = BS_SIZE/FRAME_SIZE;
	metaTable.row[pageTableID][1] = BS_SIZE/FRAME_SIZE;
	metaTable.freeRows++;

	return(0);
}


void squishPageTable(){
	int i = 0;
	int lastSmallestIndex = -1;		/* Indexes a page table row. */
	int currentSmallestMetaIndex = 0;	/* Indexes a meta table row. */

	for(i = 0; i < NUM_PAGETABLES - metaTable.freeRows; i++){
		int writeIndex = lastSmallestIndex + 1;
		int readIndex;
		currentSmallestMetaIndex = getSmallestIndex(lastSmallestIndex+1);
		readIndex = metaTable.row[currentSmallestMetaIndex][0];
		
		metaTable.row[currentSmallestMetaIndex][0] = writeIndex;

		while(readIndex <= metaTable.row[currentSmallestMetaIndex][1]){
			pageTable.row[writeIndex] = pageTable.row[readIndex];
			pageTable.row[readIndex] = 0;
			readIndex++;
			writeIndex++;
		}
		metaTable.row[currentSmallestMetaIndex][1] = writeIndex - 1;

		lastSmallestIndex = readIndex;

	}

	pageTable.freeEndRows = pageTable.freeRows;
	pageTable.nextAvailableIndex = BS_SIZE/FRAME_SIZE - pageTable.freeRows;
}


int getSmallestIndex(int above){
	int i = 0;
	int currentSmallest = BS_SIZE/FRAME_SIZE;
	int smallestIndex = 0;

	for(i = 0; i < NUM_PAGETABLES; i++){
		int row = metaTable.row[i][0];

		if(row >= above && row < currentSmallest){
			currentSmallest = metaTable.row[i][0];
			smallestIndex = i;
		}
	}

	return(smallestIndex);
}


int pageFault(int pageTableID, int pageNum){
	int swapIndex;

	/* Check if the arguments are valid. */
	if(pageNum < metaTable.row[pageTableID][0] || pageNum > metaTable.row[pageTableID][1] || pageTableID < 0){
		return(-2);
	}

	/* A page fault actually occured. */
	if(is_in_swaptable(get_page_address(&pageTable.row[pageNum])) == -1){
		swapIndex = nodeFault();
		swapTable.row[swapIndex] = get_page_address(&pageTable.row[pageNum]);
		return(0);
	}

	/* The page was already in RAM. */
	else{
		return(-1);
	}
}

int access(int pageTableID, int pageNum){
	int result;

	/* Check if the arguments are valid. */
	if(pageNum < metaTable.row[pageTableID][0] || pageNum > metaTable.row[pageTableID][1] || pageTableID < 0){
		return(-2);
	}
	result = is_in_swaptable(get_page_address(&pageTable.row[pageNum]));

	/* The page is in RAM. */
	if(result != -1){
		accessNode(199-result);
		return(1);
	}

	/* Page fault occured. */
	else{
		return(pageFault(pageTableID, pageNum));
	}
}


int is_in_swaptable(short unsigned int address){
	int i;
	for(i = 0; i < (RAM_SIZE/FRAME_SIZE)-NUM_SYSTEM_FRAMES; i++){
		if(swapTable.row[i] == address)
			return i;
	}
	return -1;
}
